Ja, zum Material.

Die Random Access Maschine. Die kennen Sie aus BFS, wenn mich nicht alles täuscht.

Das heißt, ich wiederhole das hier kurz. Einige gibt es, die aus anderen Studien

kennen kommen, die das vielleicht nicht kennen und sicher haben das nicht mehr alle

perfekt parat und außerdem gibt es Varianten.

Der Hauptpunkt an der Random Access Maschine, der Sie unterscheidet von der

Turing Maschine ist ihr Speichermodell. Also, Recall. Ja, wie sieht der Speicher

einer Random Access Maschine aus?

Die imitiert so ein bisschen einen richtigen Prozessor.

Das heißt, sie hat zum einen internen Speicher eine feste Anzahl von Registern

K Stück.

Zum anderen hat sie einen globalen Speicher, realistischerweise unbegrenzter

Größe. Ja, so unrealistisch ist es gar nicht. Im Zweifelsfalle wird der Benutzer

losgeschickt neuen Speicher kaufen.

Dieser Speicher besteht aus Speicherzellen.

Die sind irgendwie durch Zahlen adressiert. Diese Adressierungsoperation

schreibe ich mit eckigen Klammern. Ja, gut, treten wir einen Schritt kurz zurück

und überlegen uns, was unterscheidet das Ding von einer Turing Maschine.

Eine Turing Maschine speichert sämtliche Daten auf einem Band und wenn ich an die

Daten ran will, dann muss ich den Lesekopf das Band entlang bis zu der

Zelle bewegen, die ich lesen will. Mit anderen Worten, Zugriff dauert linear

lange. Ja, also wenn ich auf die ITE Speicherzelle zugreifen will, dann muss ich

immer diesen Kopf nach rechts bewegen. Das ist, solange ich nur an Dingen wie

polinomierter Zeit interessiert bin, egal. Gut, ich habe halt einen linearen Faktor

N mehr. Polinomiell bleibt polinomiell. Ja, das ist aber trotzdem letztlich keine

wirklich realistische Schätzung des Speicherverbrauchs. Ja, also wenn ich in

einem richtigen Computer auf eine Speicherzelle zugreife, dann läuft da

kein Zähler irgendwie durch alle Speicherzellen vorher durch, bis er endlich

nun bei der ist, die er lesen will, sondern da wird eben die Adresse der

Speicherzelle irgendwo angelegt und dann kriege ich das.

Und mehr oder weniger das leistet dieses Modellmodul und paar Details, die wir

gleich am Ende noch diskutieren. Dieses Modell, das gestattet mir eben hier,

wir sehen gleich wie genau, einfach eine Zahl anzugeben, i und auf diese Speicherzelle

greife ich direkt zu in Zeit 1.

Ja, das ist der Speicher. Gut, wie sieht das Programm aus?

Also Programm ist schlicht und einfach eine Liste von Anweisungen, die ich so

hintereinander runterschreibe. Also Basic, nicht Pascal. Das kennen Sie alle schon

gar nicht mehr. Das ist also unstrukturiertes Programmieren.

Ja, also ich könnte ja ein Pascal-Programm, könnte ich nicht einfach als

eine Liste von Anweisungen auffassen, weil da so Dinge drin sind, wild steifen und

tief geschachtelt ist, if und so was. Ja, also ein Pascal-Programm ist im

Wesentlichen baumförmig, wogegen also das typische Assembler- oder Basic-Programm

oder meinetwegen auch Fortran, obwohl Fortran hat wild schleifen, glaube ich,

im Wesentlichen aufgefasst werden kann als eine Liste von Anweisungen, die ich

einfach hintereinander runterschreibe.

Weil es unstrukturiert ist, kommen natürlich Sprünge vor. Irgendwie muss ich

ja einen Programmablauf da rein kriegen.

Dann kann ich mir natürlich vorstellen, dass diese Sprünge schlicht und einfach

in irgendwelche Nummern in dieser Liste gehen und das ist letztlich auch die, also

für Meta-Analyse von solchen Dingern, das, was man eigentlich unterstellt. Aber man